package NewCoder;

public class BM30 {
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree==null || pRootOfTree.left==null&&pRootOfTree.right==null){
            return pRootOfTree;
        }

        //先将左树进行转换，转换为双向链表
        TreeNode left=Convert(pRootOfTree.left);
        //找到尾节点 将他与根节点连接
        TreeNode leftTail=left;
        while(leftTail!=null && leftTail.right!=null){
            leftTail=leftTail.right;
        }
        //此时的leftTail指向左子树转换的双向链表的尾节点
        if(leftTail!=null) {
            leftTail.right = pRootOfTree;
            pRootOfTree.left = leftTail;
        }
        //继续处理转换右子树
        TreeNode rightHead=Convert(pRootOfTree.right);
        if (rightHead!=null) {
            pRootOfTree.right = rightHead;
            rightHead.left = pRootOfTree;
        }
        return left==null?pRootOfTree:left;

    }
}
